package com.njupt.Tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/11/27 16:42
 * @Description: 100. 相同的树
 * @Version: 1.0
 */


public class IsSameTree {

    /**
     * 递归算法
     * @param p
     * @param q
     * @return
     */
    public static boolean isSameTree(TreeNode p, TreeNode q) {
        if( (p == null && q != null)
                || (p != null && q== null)){
            return false;
        }else if(p == null && q == null) {
            return true;
        } else if (p.val != q.val) {
            return false;
        }
        boolean left = isSameTree(p.left, q.left);
        boolean right = isSameTree(p.right, q.right);
        return left && right;

    }


    public static boolean isSameTree1(TreeNode p, TreeNode q) {
        Deque<TreeNode> pStack = new LinkedList<>();
        Deque<TreeNode> qStack = new LinkedList<>();
        TreeNode pCur = p;
        TreeNode qCur = q;
        while( ((pCur != null || !pStack.isEmpty())
                || qCur != null || !qStack.isEmpty())){
            if(pCur != null && qCur != null){
                if(pCur.val != qCur.val){
                    return  false;
                }
                pStack.push(pCur);
                pCur = pCur.left;

                qStack.push(qCur);
                qCur = qCur.left;
            } else if ((pCur == null && qCur != null) ||
                        pCur != null && qCur == null) {
                return false;
            }else {
                pCur = pStack.pop();
                pCur = pCur.right;

                qCur = qStack.pop();
                qCur = qCur.right;
            }
        }
        return  true;

    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(2);
        root1.right = new TreeNode(1);

        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(1);
        root2.right = new TreeNode(3);

//        TreeNode root1 = new TreeNode(1);
//        root1.left = new TreeNode(2);
//        TreeNode root2 = new TreeNode(1);
//        root2.right = new TreeNode(2);

        System.out.println(isSameTree1(root1, root2));

    }
}
